package likouJava;

import javax.management.Query;
import java.util.LinkedList;
import java.util.Queue;

public class 腐烂的橘子 {
    public int orangesRotting(int[][] grid) {
        if(grid == null || grid.length == 0 || grid[0] == null) {
            return -1;
        }

        int m = grid.length, n = grid[0].length;
        Queue<int[]> queue = new LinkedList<>();
        int fresh = 0;
        int min = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 2){
                    queue.offer(new int[]{i, j});
                } else if (grid[i][j] == 1) {
                    fresh++;
                }
            }
        }
        //如果没有新鲜橘子,返回0
        if (fresh == 0){
            return 0;
        }

        int[] dirs = {-1,0, 0,1, 1,0, 0,-1};

        while (!queue.isEmpty()){
            int size = queue.size();

            for (int i = 0; i < size; i++) {
                int[] rotten = queue.poll();
                int x = rotten[0], y = rotten[1];

                for (int d = 0; d < 4; d++){
                    int nx = x + dirs[d * 2];
                    int ny = y + dirs[d * 2 + 1];

                    //判断边界和新鲜橘子
                    if (nx >= 0 && nx < m && ny >= 0 && ny < n && grid[nx][ny] == 1){
                        grid[nx][ny] = 2;
                        queue.offer(new int[] {nx,ny});
                        fresh--;
                    }
                }
            }
            min++;
            if (fresh == 0){
                return min;
            }
        }
        return -1;
    }

}
